820 - Internet bandwidth/820.2.cpp

   1 /*
   2   Ensayando una implementación un poco diferente.
   3   Encuentra el flujo máximo pero no permite reconstruir
   4   la red de flujos, i.e, no sé cuanto material fluye de
   5   i a j.
   6
   7   Accepted.
   8  */
   9 #include <iostream>
  10 #include <iterator>
  11 #include <queue>
  12 #include <stdio.h>
  13
  14 using namespace std;
  15
  16 const int MAXN = 101;
  17
  18 int cap[MAXN+1][MAXN+1], prev[MAXN+1];
  19
  20 int fordFulkerson(int n, int s, int t){
  21   int ans = 0;
  22   while (true){
  23     fill(prev, prev+n, -1);
  24     queue<int> q;
  25     q.push(s);
  26     while (q.size() && prev[t] == -1){
  27       int u = q.front();
  28       q.pop();
  29       for (int v = 0; v<n; ++v)
  30         if (v != s && prev[v] == -1 && cap[u][v] > 0)
  31           prev[v] = u, q.push(v);
  32     }
  33
  34     if (prev[t] == -1) break;
  35
  36     int bottleneck = INT_MAX;
  37     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  38       bottleneck = min(bottleneck, cap[u][v]);
  39     }
  40     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  41       cap[u][v] -= bottleneck;
  42       cap[v][u] += bottleneck;
  43     }
  44     ans += bottleneck;
  45   }
  46   return ans;
  47 }
  48
  49 int main(){
  50   int n, runs = 1;
  51   while (scanf("%d", &n) == 1 && n){
  52     for (int i=0; i<n; ++i){
  53       fill(cap[i], cap[i]+n, 0);
  54     }
  55     int s, t, C;
  56     scanf("%d %d %d", &s, &t, &C);
  57     --s, --t;
  58     while (C--){
  59       int i, j, k;
  60       scanf("%d %d %d", &i, &j, &k);
  61       cap[--i][--j] += k, cap[j][i] += k;
  62     }
  63
  64     printf("Network %d\nThe bandwidth is %d.\n\n", runs++, fordFulkerson(n, s, t));
  65   }
  66   return 0;
  67 }